package OthersQuestions.q01_bitDanceInterview;

import java.util.Arrays;

public class Solution_3 {
    int k, num = 0, max = 0; // 假定给定的k为正数，无法组成比k小的数时返回0
    int[] nums;
    public int largestLessThanK(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        Arrays.sort(nums); // 排序，后续剪枝的关键
        backtrack();
        return max;
    }
    private void backtrack() {
        for(int i = 0; i < nums.length; i++) {
            num = num * 10 + nums[i];
            if(num > k) { // 剪枝：返回上层
                num = (num - nums[i]) / 10;
                return; // 已经排序可直接return
            }
            if(num > max) max = num;
            backtrack();
            num = (num - nums[i]) / 10; // 撤销
        }
    }

}
